#include<iostream>
#include<string>
#include<stack>
using namespace std;


//Definition for singly - linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if ( head == NULL || head->next == NULL) {
            return true;
        }
        int len = 0;
        while (head != NULL) {
            head = head->next;
            len++;
        }
        stack<ListNode> S;
        int num = len/2;
        int i = 0;
        
        while (i < num) {
            S.push(*head);
            head = head->next;
            i = i + 1;
        }
        while (head != NULL) {
            if (len % 2 == 0) {
                if (S.top().val == head->val) {
                    S.pop();
                    head = head->next;
                }
                else {
                    return false;
                }
            }
            else {
                
                if (S.top().val == head->next->val) {
                    S.pop();
                    head = head->next;
                }
                else {
                    return false;
                }
            }
        }
        return true;

    }
};


//int main() {
//    ListNode p1(1);
//    ListNode p2(2);
//    /*ListNode p3(2);
//    ListNode p4(1);*/
//    p1.next = &p2;
//   /* p2.next = &p3;
//    p3.next = &p4;*/
//    Solution S;
//    bool T = S.isPalindrome(&p1);
//    cout << T << endl;
//}